package arrays;

/**
 * @author pengfei.hpf
 * @date 2020/3/31
 * @verdion 1.0.0
 */
public class SortArray {

    int[] temp;
    public int[] sortArray(int[] nums) {
        if(nums == null || nums.length == 0){
            return nums;
        }
        temp = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }
    private void mergeSort(int[] nums, int start, int end){
        if(start >= end){
            return;
        }
        int mid = (start + end)/2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid+1, end);
        merge(nums, start, mid, end);
    }

    private void merge(int[] nums, int start, int mid, int end){
        for(int i = start; i <= end; i++){
            temp[i] = nums[i];
        }
        int i = start;
        int j = mid + 1;
        int index = start;
        while(index <= end){
            if(i > mid){
                nums[index] = temp[j++];
            } else if( j > end){
                nums[index] = temp[i++];
            } else if(temp[i] > temp[j]){
                //TODO: 自己计算的时候 每一个值都要考虑进去!!!!!! 到底谁不会变 谁会变!!!!!!
                nums[index] = temp[j++];
            } else {
                nums[index] = temp[i++];
            }
            index ++;
        }
    }

    public static void main(String[] args){
        System.out.println(new SortArray().sortArray(new int[]{1,2,1,0}));
    }
}
